This invention pertains to the art of data processing systems and, more particularly, to error diffusion for rendering continuous tone images to a binary pattern of dots for the purpose of printing or displaying on a binary output device. The invention is specifically applicable to a processing system for the more efficient handling of an error innovation sequence generated by an error diffusion technique and the compression of accumulated error values from the sequence to reduce storage size in a line buffer. The invention provides the significant advantages of increased memory efficiency and reduced memory size, and the avoidance of a need for an external memory to a processor chip, for a binary printing or display device. However, it will be appreciated by those skilled in the art that the invention could be readily adapted for use in other applications as, for example, where similar data streams are sequentially accumulated for storage in a line buffer type of register.
Error diffusion is a well known technique for rendering continuous tone images to patterns of dots for the purpose of printing or displaying on a binary device. The error diffusion technique is often the preferred technique of rendering for low to medium resolution devices (under 600 dots per inch), particularly since the error diffusion method does not embody a predetermined threshold array as in the traditional clustered dot screening techniques. The lack of any such structured cell enables the error diffusion to rapidly track the input data positions, making it better capable of rendering high frequency detail. The alternative methods require large size arrays to accommodate as sufficient a number of gray levels as are needed for high quality reproduction (it has been determined that the human eye can distinguish between some 200 shades of gray). Such large size arrays can become visually noticeable in the output; thus, the array size, and the corresponding number of gray levels, must be compromised against the desired image quality.
The error diffusion method typically involves a single pass with a scanning device over the input image, during which each pixel is processed sequentially. The conventional process consists of thresholding the input pixel value and replacing it with one of two values, on or off. As each pixel is so changed, an error is introduced to the local gray level of the image. The error is the difference in gray level between the scan determined original pixel value and the "on" or "off" density printed or displayed value. This error is diffused to neighboring pixels by adjusting the values of the neighboring pixels to preserve the local gray level prior to thresholding that had appeared to the eye of the viewer. In order to avoid multiple passes over the image, the error is only propagated (or "diffused") among future pixels that have not yet been processed (e.g., to pixels located to the right and below the current pixel for a left-to-right scan order). Several methods for determining how to distribute the error among the neighboring pixels are well known.
FIG. 2 demonstrates the principles of the error diffusion technique with a particular well known filter scheme. It should be noted the FIG. 2 diffusion scheme was originally derived by Floyd & Steinberg, and are included here only for the purpose of illustration. However, this example can still demonstrate the technique of the subject invention, its implementation, and can be used to clearly illustrate the differences between the subject invention and conventional error diffusion techniques.
In FIG. 2, the squares 10 represent the input image pixels on a raster grid as determined from an input scanning device. The pixels in black and white 12, 14 were already processed, thresholded, and binarized to be either on or off. The shaded pixels 16 have not yet been processed. The center pixel 18, surrounded by a dark frame, is the pixel to be processed next. The arrows leading from the current pixel to weighted values 1, 3, 5 and 7 indicate how the current threshold error is to be distributed to the neighboring pixels. It is often referred to as the "error diffusion filter" in the literature because the application of a specific weighting scheme is in effect a filtering of the calculated error between what the scanner detects and the printer prints for each pixel. The numbers along the arrows describe the possibly varying! non-normalized relative neighbor weight. For example, the number 7 associated with the pixel immediately to the right of the current pixel 18 indicates that 7/16 of the error will be used to adjust this pixel, where 16 is the normalization factor equal to the total sum of the weights. As each of these neighbors is so adjusted, its associated gray value is changed (making it darker or lighter, depending on the sign of the error), and the updated value is what will be used for thresholding the neighboring pixels.
Based on the above description, a conventional error diffusion technique is composed of the following three basic steps:
first, a thresholding step, in which the current original pixel value is compared with a given threshold to determine the output for the printing or displayed pixel;
second, an error calculation step, where the error is calculated by subtracting the binary output level from the original pixel value; and
third, the error is filtered according to the selected weighting scheme and distributed to the neighboring pixels.
This process then advances by one pixel and repeats, until the end of a line is reached.
The conventional error diffusion process is illustrated in FIG. 3. The notation here is that x(i,j) is the current pixel value, e(i,j) is the error and .DELTA.x(i,j) is the compensation value to the pixel at location (i,j). Also, small rectangles represent data registers, bold lines indicate buses and thin lines indicate binary values.
As can be seen from FIG. 3, the conventional method requires multiple accesses to a memory to accumulate the sequence of compensation values. For each pixel processed, the system needs to read in a number of error values for neighboring pixels, modify them and write the results back to the memory. This is clearly inefficient, as the value of every pixel must be so adjusted multiple times. For example, the value of the shaded pixel labeled 5 in FIG. 2 will be "read-modified-written" once for the error generated in the current cycle, only to be "read-modified-written" again when the process moves onto the next pixel (this time via the 3 filter weight, assuming a left-to-right process).
The repetitive access to the memory is costly in terms of time consumption and inefficient in data handling and is one specific problem sought to be overcome by the subject invention.
Another particular problem with a conventional error diffusion system is memory size. The amount of memory needed to store and accumulate relevant error values for a raster scan is such that an external memory to a processing chip usually has to be employed. Again, the inefficiencies of accessing external memory, as well as the additional costs involved, presents a substantial need to minimize the amount of context memory employed for any real time application of an error diffusion technique.
The error diffusion method illustrated in FIG. 3 requires storing at least one line of context in memory, due to the fact that the current pixel error directly modifies the values of pixels below it, about one scanline away. In practice, this context can be quite large. A typical 8.5 inch wide four color page printed at 600 dpi, for example, would require keeping at least 20,000 cells of data in memory, with each cell large enough to contain all the information needed to process one single pixel. For reasons detailed below, the usage of eight bits of precision per cell may not be sufficient. Assuming that 12 bits per cell are used, the overall storage requirement for this example translates to some 30 K bytes of memory. Such storage sizes are not cost effective to implement on a single chip using current low-cost silicon technology, and are much better utilized using external memory devices. It is therefore also substantially needed to reduce the overall system cost by applying compression techniques to significantly reduce the cell size, thereby lowering the total memory size, without comprising the image quality.
Considering the minimum cell size, it is well known that the human visual perception system cannot distinguish more than about 200 shades of gray, implying that 8 bits per pixel is adequate for gray scale image representation. Current practice typically uses the 8 bit system to compactly encode each continuous tone image separation. Thus, color images are typically encoded using three 8-bit separations or more, e.g., three as in "red, green and blue" or "cyan, magenta and yellow"; four as in "cyan, magenta, yellow and black"; or even more with hi-fidelity color reproduction. The 8 bit system does not have the capability to handle the error filtration and feedback mechanism discussed above. The value of any single pixel error can be as large as the largest absolute difference between the compensated gray level and the threshold, where the latter may also be varying through the process as part of several other enhancement techniques. The total sum of error contributions to any given pixel depends on the image content and past error propagation history, and may occasionally add up to a large value. Also, these contributions can be negative or positive, while pixel values are considered to be positive integers only. When added to the neighboring pixel values, these contributions may well cause the overall result to overflow the 8 bit range and even become too large, or negative. Hence larger ranges, i.e., more bits, are usually needed.
Furthermore, noise may also have to be injected as a common practice to eliminate various rendering artifacts, thus contributing to increase the size of the error values. The Floyd & Steinberg method illustrated above employs a deterministic error diffusion filter. That is, the way the error is distributed to the neighboring pixels remains constant and fixed for all pixels. Floyd & Steinberg, based on experimentation, concluded that the filter shown in FIG. 2 has the minimum filter size (in terms of the number of weights) required for producing acceptable rendering quality. However, rendering artifacts may remain visible at the output, particularly at some specific gray levels. These artifacts are typically manifested as "worming artifacts", where several stray dots appear, in the viewers mind, to be connected in the form of short line segments. One effective method to further eliminate these artifacts is to inject additional pseudo-random noise in the process. The noise helps to "dither" the dot positions around with respect to the threshold, thereby breaking apart the line segment structures into smaller, less visible ones. Larger noise levels may be more effective to eliminate the said artifacts, but may also lead to an increase in the apparent level of "graininess" of the image. This is the reason why 10 to 12 bits per error value are often used in common practice.
Due to the random nature of the error diffusion technique and the associated high-frequency content, it is well known that it is relatively difficult to compress error diffused images. Most standard compression techniques available will fail to produce a significant compression ratio. The same generally holds true for compression of the error sequence, although there is an obviously large reduction in information content in going from an 8 bit continuous tone image to binary output on paper or display.
The present invention contemplates a new and improved apparatus and method which overcomes all the above-referred to problems and others to provide a new error diffusion system which is economical to manufacture, readily adaptable to a plurality of diffusion techniques having a variety of dimensional data characteristics and which provides improved compression of the residual error streams and more efficient handling of the memory in a preferred error diffusion technique.